/*
https://leetcode.cn/problems/parallel-courses-ii/solution/yu-niang-niang-1494-bing-xing-ke-cheng-i-duny/
 */
import java.util.Arrays;

public class Solution1494 {
    public int minNumberOfSemesters(int n, int[][] relations, int k) {
        int[] f=new int[1<<n];
        Arrays.fill(f,Integer.MAX_VALUE);
        f[0]=0;
        for (int i=0;i<1<<n;i++){
            if (f[i]==Integer.MAX_VALUE){
                continue;
            }
            int now=0;
            for (int j=0;j<n;j++){
                if ((i&(1<<j))==0){
                    boolean flag=true;
                    for (int[] relation : relations) {
                        if (relation[1]-1==j){
                            if ((i&(1<<(relation[0]-1)))==0){
                                flag=false;
                                break;
                            }
                        }
                    }
                    if (flag){
                        now|=1<<j;
                    }
                }
            }
            int t=now;
            do{
                if (Integer.bitCount(t)<=k){
                    f[i|t]=Math.min(f[i|t],f[i]+1);
                }
                t=(t-1)&now;
            }while (t!=now);
        }
        return f[(1<<n)-1];
    }

    public static void main(String[] args) {
        System.out.println(new Solution1494().minNumberOfSemesters(4,new int[][]{{2,1},{3,1},{1,4}},2));
    }
}
